package chapter02;

import org.w3c.dom.Node;

import java.util.*;


public class Merge56 {
    /**
     * 排序+指针
     * 按照区间左边界从小到大排序 再按右边界从小到大排序
     * 初始化左边界left==intervals[0][0] 右边界right==intervals[0][1]
     * 已有区间[left,right]
     * 遍历区间数组 i->[1,length-1]
     * 合并区间
     *   1) 当前遍历的区间的左边界小于right
     *      a.当前遍历的区间的右边界大于right
     *        改变区间右边界范围  [left,当前区间的右边界]
     *   2) 否则
     *      说明当前区间不在已有区间范围内
     *      将已有区间加入list
     *      将当前遍历的区间赋给已有区间
     * 遍历区间结束后 最后一个已有区间没有放到list 需要额外加入
     * 将list转为数组即可
     */
    class Comp implements Comparator<int[]>{
        public int compare(int[] o1, int[] o2) {
            if(o1[0]==o2[0]){
                return o1[1]-o2[1];
            }else{
                return o1[0]-o2[0];
            }
        }
    }
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, new Comp());
        int left=intervals[0][0];
        int right=intervals[0][1];
        List<int[]> list=new ArrayList<>();
        int length=intervals.length;
        for(int i=1;i<length;i++){
            if(intervals[i][0]<=right){
                if(intervals[i][1]>right){
                    right=intervals[i][1];
                }
            }else{
                list.add(new int[]{left,right});
                left=intervals[i][0];
                right=intervals[i][1];
            }
        }
        list.add(new int[]{left,right});
        return list.toArray(new int[0][0]);
    }
}
